Proximity Search in Databases.
Roy Goldman, Narayanan Shivakumar, Suresh Venkatasubramanian, Hector Garcia-Molina:
Proximity Search in Databases.
VLDB 1998: 26-37@inproceedings{DBLP:conf/vldb/GoldmanSVG98,
author = {Roy Goldman and
Narayanan Shivakumar and
Suresh Venkatasubramanian and
Hector Garcia-Molina},
editor = {Ashish Gupta and
Oded Shmueli and
Jennifer Widom},
title = {Proximity Search in Databases},
booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
Large Data Bases, August 24-27, 1998, New York City, New York,
USA},
publisher = {Morgan Kaufmann},
year = {1998},
isbn = {1-55860-566-5},
pages = {26-37},
ee = {db/conf/vldb/GoldmanSVG98.html},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
An information retrieval (IR) engine can rank documents based on textual proximity of keywords within each document. In this paper we apply this notion to search across an entire database for objects that are "near" other relevant objects. Proximity search enables simple "focusing" queries basedon general relationships among objects, helpful for interactive query sessions. We view the database as a graph, with data in vertices (objects) andrelationships indicated by edges. Proximity is defined based on shortest paths between objects. We have implemented a prototype search engine that uses this model to enable keyword searches over databases, and we have found it very effective for quickly finding relevant information. Computing the distance between objects in a graph stored on disk can be very expensive. Hence, we show how to build compact indexes that allow us to quickly find the distance between objects at search time. Experiments show that our algorithms are efficient and scale well.
Copyright © 1998 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.):
VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA.
Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents
References
- [AHU74]
- Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:
The Design and Analysis of Computer Algorithms.
Addison-Wesley 1974, ISBN 0-201-00029-6
![bibliographical record in XML](../../xml.gif)
- [AKR93]
- ...
- [Bod96]
- Hans L. Bodlaender:
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth.
SIAM J. Comput. 25(6): 1305-1317(1996)
![bibliographical record in XML](../../xml.gif)
- [Con97]
- ...
- [CZ95]
- Shiva Chaudhuri, Christos D. Zaroliagis:
Shortest Path Queries in Digraphs of Small Treewidth.
ICALP 1995: 244-255
![bibliographical record in XML](../../xml.gif)
- [DGEP98]
- Shaul Dar, Gadi Entin, Shai Geva, Eran Palmon:
DTL's DataSpot: Database Exploration Using Plain Language.
VLDB 1998: 645-649
![bibliographical record in XML](../../xml.gif)
- [Dij59]
- ...
- [DM97]
- Stefan Deßloch, Nelson Mendonça Mattos:
Integrating SQL Databases with Content-Specific Search Engines.
VLDB 1997: 528-537
![bibliographical record in XML](../../xml.gif)
- [DR94]
- Shaul Dar, Raghu Ramakrishnan:
A Performance Study of Transitive Closure Algorithms.
SIGMOD Conference 1994: 454-465
![bibliographical record in XML](../../xml.gif)
- [Fag96]
- Ronald Fagin:
Combining Fuzzy Information from Multiple Systems.
PODS 1996: 216-226
![bibliographical record in XML](../../xml.gif)
- [Flo62]
- ...
- [Goo61]
- ...
- [GSVGM98]
- ...
- [HKRS94]
- Philip N. Klein, Satish Rao, Monika Rauch Henzinger, Sairam Subramanian:
Faster shortest-path algorithms for planar graphs.
STOC 1994: 27-37
![bibliographical record in XML](../../xml.gif)
- [KS]
- ...
- [LT80]
- Richard J. Lipton, Robert Endre Tarjan:
Applications of a Planar Separator Theorem.
SIAM J. Comput. 9(3): 615-627(1980)
![bibliographical record in XML](../../xml.gif)
- [MAG+97]
- Jason McHugh, Serge Abiteboul, Roy Goldman, Dallan Quass, Jennifer Widom:
Lore: A Database Management System for Semistructured Data.
SIGMOD Record 26(3): 54-66(1997)
![bibliographical record in XML](../../xml.gif)
- [Ora97]
- ...
- [Pel97]
- ...
- [PGMW95]
- Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom:
Object Exchange Across Heterogeneous Information Sources.
ICDE 1995: 251-260
![bibliographical record in XML](../../xml.gif)
- [Sal89]
- Gerard Salton:
Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer.
Addison-Wesley 1989, ISBN 0-201-12227-8
![bibliographical record in XML](../../xml.gif)
- [Ull89]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
![bibliographical record in XML](../../xml.gif)
- [UY91]
- ...
- [ZMSD93]
- Justin Zobel, Alistair Moffat, Ron Sacks-Davis:
Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files.
VLDB 1993: 290-301
![bibliographical record in XML](../../xml.gif)
Copyright © Sun Mar 14 23:31:29 2010
by Michael Ley (ley@uni-trier.de)