Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-06-29
2008-05-06
Rimell, Sam (Department: 2161)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07370054
ABSTRACT:
One embodiment of the present invention provides a system that implements a hash table that is fully dynamic and lock-free. During a lookup in the hash table the system first uses a hash key to lookup a bucket pointer in a bucket array. Next, the system follows the bucket pointer to a data node within a linked list that contains all of the data nodes in the hash table, wherein the linked list contains only data nodes and at most a constant number of dummy nodes. The system then searches from the data node through the linked list to locate a node that matches the hash key, if one exists.
REFERENCES:
patent: 5671446 (1997-09-01), Rakity et al.
patent: 5960434 (1999-09-01), Schimmel
patent: 6067547 (2000-05-01), Douceur
patent: 6654773 (2003-11-01), Hills
patent: 2001/0042204 (2001-11-01), Blaker et al.
patent: 2004/0107227 (2004-06-01), Michael
Maged, Michael M., “High Performance Dynamic Lock-Free Hash Tables and List-Based Sets.” Aug. 2002, ACM Press.
Shalev, Ori and Nir Shavit, “Split-Ordered Lists: Lock-Free Extensible Hash Tables.” Jul. 13-16, 2003 ACM Press.
Harris, Timothy L., “A Pragmatic Implementation of Non-Blocking Linked-Lists.” Oct. 2001, Proceedings of the 15th International Symposium on Distributed Computing.
Publication entitled “Concurrent Set Manipulation Without Locking”, by Vladimir Lanin et al., 7th ACM Symposium on the Principlies of Database Systems, pp. 211-220, Mar. 1988.
Publication entitled “DCAS-Based Concurrent Deques”, by Ole Agesen et al., 12thAnnual ACM Symposium on Parallel Algorithms and Architectures, Jul. 2000.
Publication entitled “Dynamic Lock-Free Deques Using Single-Address Double-Word CAS”, by Maged M. Michael, Annual ACM Symposium on Principles of Distributed Computing Proceedings of the twenty-first annual symposium on Principles of distributed computing, session 1, pp. 24-30, 2002, ISBN:1-58113-485-1.
Publication entitled “A Lock-Free Mechanism for Supporting Dynamic-Sized Data Structures”, Maurice Herlihy et al., Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), Jul. 2003.
Publication entitled “Trie Hashing With Controlled Load”, by Witold A. Litwin et al., IEEE Transactions on Software Engineering, vol. 17, No. 7, Jul. 1991.
Publication entitled “Split-Ordered Lists—Lock-free Resizable Hash Tables”, by Ori Shalev et al., Proceedings of the Twenty-Second ACM Symposium on Principles of Distributed Computing, pp. 102-111, Jul. 13-16, 2003, Boston Massachusetts.
Publication entitled “The Repeat Offender Problem: A Lock-Free Mechanism for Supporting Dynamic-Sized Data Structures”, by Maurice Herlihy et al., SUN Microsystems, Inc., Report TR-2002-112, Jul. 2002.
Publication entitled “A Pragmatic Implementation of Non-Blocking Linked-Lists”, by Timothy L. Harris, Proceedings of the 15thInternational Symposium on Distributed Computing, Oct. 2001, pp. 300-314.
Publication entitled “Non-Blocking Algorithms and Preemption-Safe Locking on Multiprogrammed Shared Memory Multiprocessors”, by Maged M. Michael, Journal of Parallel and Distributed Computing 51(1), pp. 1-26, 1998.
Publication entitled “Using Local-Spin k-Exclusion Algorithms to Improve Wait-Free Object Implementations”, by James H. Anderson et al., The University of North Carolina and University of Pittsburgh, Nov. 1995, revised 1996.
Publication entitled “Lock-Free Linked Lists Using Compare-and Swap”, by John D. Valois, Renssealaer Polytechnic Institute, Annual ACM Symposium on Principles of Distributed Computing, pp. 214-222, ISBN 0-89791-710-31995 valoisj@cs.rpi.edu.
Publication “Trie Hashing”, by Witold Litwin, I.N.R.I.A. 78-153 Le Chesnay, France, 1981, International Conference on Management of Data, pp. 19-29, ISBN 0-89791-040-0.
Publication “Non-Blocking Timeout in Scalable Queue-Based SpinLocks” by Michael L. Scott, Dept. of Computer Science, Univeristy of Rochester, Rochester, NY 14627-0226, Feb. 2002, scott@cs.rochester.edu www.cs.rochester.edu/u/scott/synchronization/.
Publication “Practical Implementations of Non-Blocking Synchronization Primitives”, by Mark Moir, Dept. of Computer Science, University of Pittsburgh, Annual ACM Symposium on Principles of Distributed Computing, 1997, pp. 219-229. moir@cs.pitt.edu.
Publication “Skiplist-Based Concurrent Priority Queues” by I. Lotan of Stanford University and N. Shavit of Sun Microsystems Laboratories, http://ipdps.eece.unm.edu/2000/papers/shavit/pdf.
Publication “Concurrent Maintenance of Skip Lists” by William Pugh, Institute of Advanced Computer Studies, University of Maryland, Computer Science Technology Report Series, Apr. 1989, revised Jun. 1990.
Publication “Non-Blocking k-Compare-Single-Swap” by Victor Luchangco Sun Microsystems Laboratories and Nir Shavit School of Computer Sciences Tel Avis University, shanir@cs.tau.ac.il http://research.sun.com/people/moir/Papers/p004-luchangco.pdf.
Luchangco Victor
Maessen Jan-Willem
Martin Paul A.
Bibbee Jared M
Park Vaughan & Fleming LLP
Rimell Sam
Sun Microsystems Inc
LandOfFree
Method and apparatus for indexing a hash table which is... 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 indexing a hash table which is..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for indexing a hash table which is... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3987360