Re: Creating and saving IDs - is there a theory?

Doug Dumitru wrote: > "Lior Messinger" <messingr@netvision.net.il> wrote: > >We are designing a project where we need to create, save and then verify > >huge amounts of IDs (or serial numbers), for inventory items. We need to do > >the saving part and the verification very fast, on a server. This is done > >to verify that the items are not faked. The project is done on NT and Unix. > >Is there any theory about doing that? > > From a purely theoretical point of view, you need an application that can > maintain a very fast "direct hit" index. Basically, it sounds as though you > wish to "put something in a store" and then very quickly, determine if the > something is present. > > The most typical way of accomplishing this is with a hashing algorithm. Hashing > is far and away the fastest indexing method when only direct hits are required > (as opposed to sequential access). An example of hashing is the lookup > functions in large TCP/IP routers that get information for a particular IP > subnet path. This is probably the most extreme example of a lookup needing to > run quickly. The initial question, and this answer, are both based on the opinion that you have to look up the ID to verify it. Couldn't it be much faster, and still sufficient, to have a self checking ID? By this I mean an ID that contains redundant information that is used for a consistency check. Numbers on a bank-note are created like that: you don't have to ask a server to find out whether a certain number is fake or not, you can decide locally. This should be the fastest way. There is some theory behind it. You might use a Modulo-11 or a dieder group based algorithm. I haven't personally read it, but in the April 1997 edition of the c't (a german computer magazine, http://www.heise.de) I found a reference to J. Verhoeff, Error Detecting Decimal Codes, Mathematical Centre Tracts, Vol. 29 (Mathematisch Centrum, Amsterdam, NL, 1969). You might also like check newer books on codes. Hope this helps! Klaus --------------- Klaus Marquardt klaus.marquardt(at)draeger.com Draegerwerk AG, Germany >Technology for Life< Disclaimer: Draeger may or may not share my opinion