Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
2011-04-12
2011-04-12
Sparks, Donald (Department: 2129)
Data processing: artificial intelligence
Knowledge processing system
C706S014000, C707S763000, C707S765000, C707S796000, C707S797000
Reexamination Certificate
active
07925604
ABSTRACT:
The embodiments of the invention provide a method of ordering an intersecting of a group of lists into a left-deep AND-tree. The method begins by performing a first selecting process including selecting a top list, corresponding to a top leaf of the left-deep AND-tree, from the group of lists to leave remaining lists of the group of lists. The top list can be the smallest list of the group of lists. The method can also select a pair of lists from the group of lists, such that the pair of lists has the smallest intersection size relative to other pairs of lists of the group of lists. Next, the method estimates intersections of the remaining lists with the top list by estimating an amount of intersection between the remaining lists and the top list. This involves sampling a portion of the remaining lists. The method also includes identifying larger list pairs having smaller intersections sizes when compared to smaller list pairs having larger intersections sizes.
REFERENCES:
patent: 5809219 (1998-09-01), Pearce et al.
patent: 6211882 (2001-04-01), Pearce et al.
patent: 7120301 (2006-10-01), Wenzel et al.
Gupta et al., “Efficient Gathering of Correlated Data in Sensor Networks”, MobiHoc'05, May 25-27, 2005.
Eppstein, et al., “Sparsification—A Technique for Speeding Up Dynamic Graph Algorithms,” Journal of the ACM, vol. 44, No. 5, Sep. 1997, pp. 669-696.
Gupta, et al., “Efficient Gathering of Correlated Data in Sensor Networks,” MobiHoc' 05, ACM, May 25-27, 2005, pp. 402-413.
Long, et al., “Three-Level Caching for Efficient Query Processing in Large Web Search Engines,” WWW 2005, ACM, May 10-14, 2005, pp. 257-266.
Aronov, et al, “Cost-Driven Octree Construction Schemes: An Experimental Study,” SoCG' 03, ACM, Jun. 8-10, 2003, pp. 227-236.
Raghavan, et al., “A Rearrangeable Algorithm for the Construction of Delay-Construction of Delay-Constrained Dynamic Multicast Trees,” IEEE/ACM Transactions on Networking, vol. 7, No. 4, Aug. 1999, pp. 514-529.
Krauthgamer Robert
Mehta Aranyak
Raman Vijayshankar
Rudra Atri
Brown, Jr. Nathan H
Gibb I.P. Law Firm LLC
International Business Machines - Corporation
Sparks Donald
LandOfFree
Adaptive greedy method for ordering intersecting of a group... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive greedy method for ordering intersecting of a group..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive greedy method for ordering intersecting of a group... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2651310