ABSTRACT Information Sharing Across Private Databases

  • 格式:pdf
  • 大小:193.06 KB
  • 文档页数:12

InformationSharingAcrossPrivateDatabasesRakeshAgrawalAlexandreEvfimievskiRamakrishnanSrikantIBMAlmadenResearchCenter650HarryRoad,SanJose,CA95120

ABSTRACTLiteratureoninformationintegrationacrossdatabasestacitlyas-sumesthatthedataineachdatabasecanberevealedtotheotherdatabases.However,thereisanincreasingneedforsharinginfor-mationacrossautonomousentitiesinsuchawaythatnoinforma-tionapartfromtheanswertothequeryisrevealed.Weformalizethenotionofminimalinformationsharingacrossprivatedatabases,anddevelopprotocolsforintersection,equijoin,intersectionsize,andequijoinsize.Wealsoshowhownewapplicationscanbebuiltusingtheproposedprotocols.

1.INTRODUCTIONInformationintegrationhaslongbeenanareaofactivedatabaseresearch[12,16,21,27,48].Sofar,thisliteraturehastacitlyas-sumedthattheinformationineachdatabasecanbefreelyshared.However,thereisnowanincreasingneedforcomputingqueriesacrossdatabasesbelongingtoautonomousentitiesinsuchawaythatnomoreinformationthannecessaryisrevealedfromeachdatabasetotheotherdatabases.Thisneedisdrivenbyseveraltrends:

End-to-endIntegration:E-businessondemandrequiresend-to-endintegrationofinformationsystems,fromthesup-plychaintothecustomer-facingsystems.Thisintegrationoccursacrossautonomousenterprises,sofulldisclosureofinformationineachdatabaseisundesirable.

Outsourcing:Enterprisesareoutsourcingtasksthatarenotpartoftheircorecompetency.Theyneedtointegratetheirdatabasesystemsforpurposessuchasinventorycontrol.

Simultaneouslycompeteandcooperate:Itisbecomingcommonforenterprisestocooperateincertainareasandcompeteinothers,whichrequiresselectiveinformationshar-ing.

Security:Governmentagenciesneedtoshareinformationfordevisingeffectivesecuritymeasures,bothwithinthesamegovernmentandacrossgovernments.However,an

CurrentlyatCornellUniversity,Ithaca,NY14853.

Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseisgrantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise,torepublish,topostonserversortoredistributetolists,requirespriorspecificpermissionand/orafee.SIGMOD2003,June9-12,2003,SanDiego,CA.Copyright2003ACM1-58113-634-X/03/06...$5.00.

agencycannotindiscriminatelyopenupitsdatabasetoallotheragencies.Privacy:Privacylegislationandstatedprivacypoliciesplacelimitsoninformationsharing.However,itisstilldesirabletomineacrossdatabaseswhilerespectingprivacylimits.Weproposeanewparadigmofminimalnecessaryinforma-tionsharingacrossprivatedatabases.Intuitively,givenadatabasequeryspanningmultipleprivatedatabases,wewishtocomputetheanswertothequerywithoutrevealinganyadditionalinformationapartfromthequeryresult.Wewillsometimesrelaxthisconstrainttoallowsomeminimaladditionalinformationtoberevealed.

1.1MotivatingApplicationsWegivetwoprototypicalapplicationstomaketheaboveparadigmconcrete.

Application1:SelectiveDocumentSharingEnterpriseisshoppingfortechnologyandwishestofindoutifenterprisehassomeintellectualpropertyitmightwanttolicense.However,wouldnotliketorevealitscompletetechnologyshoppinglist,norwouldliketorevealallitsunpublishedintellectualproperty.Rather,theywouldliketofirstfindthespecifictechnologiesforwhichthereisamatch,andthenrevealinformationonlyaboutthosetechnologies.Thisproblemcanbeabstractedasfollows.Wehavetwodatabasesand,whereeachdatabasecon-tainsasetofdocuments.Thedocumentshavebeenpreprocessedtoonlyincludethemostsignificantwords,usingsomemeasuresuchastermfrequencytimesinversedocumentfrequency[41].Wewishtofindallpairsofsimilardocumentsand,withoutrevealingtheotherdocuments.Indatabaseterminology,wewanttocomputethejoinofandusingthejoinpredi-cate,forsomesimilarityfunctionandthreshold.Thefunctioncouldbe,forinstance.Manyapplicationsmaptothisabstraction.Forexample,twogovernmentagenciesmaywanttosharedocuments,butonlyonaneed-to-knowbasis.Theywouldliketofindsimilardocumentscontainedintheirrepositoriesinordertoinitiatetheirexchange.

Application2:MedicalResearchImagineafuturewheremanypeoplehavetheirDNAsequenced.AmedicalresearcherwantstovalidateahypothesisconnectingaDNAsequencewithareac-tiontodrug.Peoplewhohavetakenthedrugarepartitionedintofourgroups,basedonwhetherornottheyhadanadversereactionandwhetherornottheirDNAcontainedthespecificse-quence;theresearcherneedsthenumberofpeopleineachgroup.DNAsequencesandmedicalhistoriesarestoredindatabasesinautonomousenterprises.Duetoprivacyconcerns,theenterprisesdonotwishtoprovideanyinformationaboutanindividual’sDNAsequenceormedicalhistory,butstillwishtohelpwiththeresearch.