DATA SEARCH METHOD USING LOCALITY

摘要

PURPOSE: A data search method using locality is provided to supply an algorithm to maximize the usefulness of cash equipping in each processor by including data in a search path. CONSTITUTION: The method comprises a minimum level calculation step and a data search step. The minimum level calculation comprises steps of setting a window corresponding to a proper cash size and cash hit frequency from the standard data having the locality, recording the number referring to each memory under a condition for desired hit frequency, and calculating the minimum level from the standard data by arranging in order of the referring number. The data search is executed in order to make the search path used frequently become short and make the search path not used become long by making the frequently used data locate in the front part of search path so as to make the level decide in a skip list by rearranging the node level If the referring number recorded to each node does not exist between the minimum referring number of present assigned level and next level on the basis of the calculated minimum level.