Method and apparatus for efficient proximity searching

Details Method and apparatus for efficient proximity searching Method and apparatus for efficient proximity searching

1999-02-26

2001-08-28

Amsbury, Wayne (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06282540

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to accessing and searching data using spatial content. More specifically, the invention relates to improved efficiency and proximity searching with spatial content based on selection criteria that contain both spatial and non-spatial attributes.
BACKGROUND OF THE INVENTION
Databases that contain geographically-oriented data are becoming increasingly common, in large part fueled by the growth of the Internet and the World Wide Web. Examples include Electronic Yellow Pages (EYP) and classified ad directories that allow users to search for businesses based on some combination of location and non-geographic attributes. In the EYP case, a user might want to locate a specific type of business, or businesses, with specific words in their name, within a given area. An online automobile classified ad system needs to locate cars with specific characteristics within a given distance from a user's home.
As spatial data becomes more common, the requirement that such data be storable and accessible with off-the-shelf hardware and software becomes mandatory. In particular, Relational Database Management systems (RDBMS) are commonly used to store and access large datasets of many varieties, including data with spatial content. RDBMS systems provide security, safety, transactional control, high speed and multi-user access, all of which are important for information systems, including World Wide Web-based information systems. RDBMS systems are also pervasive.
Research has explored access methods that efficiently support the retrieval of spatial data. Such research usually confines itself to exploring data structures and algorithms that efficiently handle the creation and retrieval of data based on spatial attributes, but not spatial attributes in conjunction with non-spatial attributes. Further, most research involves the definition of specialized storage structures and access methods without particular concern over how well the structures and access methods can be overlaid onto those provided by commercial RDBMS systems.
Quadtrees are commonly used to represent spatial data. A quadtree region is represented as a single attribute by interleaving the base-two representations of the X and Y coordinates of a two-dimensional space (more generally an n-dimensional space). Efficient retrieval of spatial data requires the mapping of an n-dimensional space into a single attribute. Without such a mapping, it would be impractical to use modem database systems, including relational database systems, as an access mechanism for large spatial databases. In some circumstances, the performance of database systems can degrade dramatically when concatenated index keys are used. Because a point or a region in space can be represented as a single attribute, quadtrees make effective use of the indexing structures supplied by modem database systems.
In at least one prior art system, when a proximity search is initiated, a search engine determines the set of regions it is prepared to search to locate the entities within the geographic search radius. In addition to proximity, an entity must match other search criteria specified by a user. The search engine examines regions in increasing distance from the search center until enough matching entities are located or all regions in the search radius have been examined. By searching regions in increasing distance from the search center, closer entities will be examined before more distance ones. If the requisite number of entities is found before examining all the regions, some regions will not have to be examined at all if the closest point on the region is further away than the entities that have already been found.
Because the regions are examined solely on the basis of proximity without knowing whether the region contains any relevant entities, the search engine spends considerable time doing unproductive work. In the case of a relational database system, searching a region involves examining an index, and perhaps some associated data buffers to examine attributes in more detail. Index searching is a relatively efficient operation, but the cumulative effect of such searching adds up. For Electronic Yellow Pages, one analysis of query logs consistently show that for keyword queries (e.g., Find businesses in this area with “Central” and “Supplies” in their names), more than 85% of the searched regions do not have any businesses with matching keywords; 58% of the total search time is wasted fruitlessly examining these regions. The numbers are only slightly better for category queries (e.g., Find Restaurants in this area).
What is needed is an improved proximity searching technique that reduces, or even minimizes, the amount of wasted searching.
SUMMARY OF THE INVENTION
A method and apparatus to improve proximity searching is described. In one embodiment, the method comprises receiving a spatial origin and at least one attribute from a user. A bitmap corresponding to the one or more attributes is retrieved. Searching of one or more quads within a distance of the spatial origin is performed, where each quad has at least one point to which the attribute(s) applies as reflected in the bitmap.


REFERENCES:
patent: 4839853 (1989-06-01), Deerwester et al.
patent: 5504889 (1996-04-01), Burgess
patent: 5537491 (1996-07-01), Mahoney et al.
patent: 5619709 (1997-04-01), Caid et al.
patent: 5710915 (1998-01-01), McElhiney
patent: 5748805 (1998-05-01), Withgott et al.
patent: 5761652 (1998-06-01), Wu et al.
patent: 5832494 (1998-11-01), Egger et al.
patent: 5864855 (1999-01-01), Ruocco et al.
patent: 5913205 (1999-06-01), Jain et al.
patent: 5915250 (1999-06-01), Jain et al.
patent: 5940825 (1999-08-01), Castelli et al.
patent: 5974412 (1999-10-01), Hazlehurst et al.
patent: 5983220 (1999-11-01), Schmitt
patent: 6021406 (2000-02-01), Kuznetsov
patent: 6047280 (2000-04-01), Ashby et al.
patent: 6081803 (2000-06-01), Ashby et al.
Kao et al., “Efficient Proximity Search in Multivariate Data”, 1998, pp. 145-154.*
Takeuchi et al., “A finegrain, current mode scheme for VLSI proximity search engine”, IEEE 1998, pp. 184-185.

Affiliated with

Also associated with

Rating

Method and apparatus for efficient proximity searching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for efficient proximity searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient proximity searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2535426