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.