104 results about "Skip list" patented technology

An allocation method and system for allocating a least-interfered communications link between a cellular mobile station and a private radio base station within a cellular system is disclosed. A set of candidate carrier frequencies are first selected and ordered by the amount of interference present within the cellular system, and a subset thereof selected. A second set of candidate frequencies and associated timeslots are then selected from the subset and ordered by the amount of interference present in the private radio system environment, and a second subset thereof selected. A plurality of discrete hop lists for each timeslot are then formed, and one of the hop lists exhibiting the least amount of interference is then selected to be applied in the communications link.

A method for constructing routing / forwarding tables for an IP address lookup using a skip list. The method comprises dividing a prefix length range of an IP address in a preset method; creating a header node having a maximum level based on a number of clusters divided into the prefix length range, the header node pointing every node in the skip list; and creating subnodes by the number of the divided clusters, the subnodes each having the divided prefix length range as a key.

An efficient and practical method for dynamically maintaining an authenticated dictionary uses a skip list data structure and communicative hash functions to provide a dictionary database (201) that stores information objects so that any individual object can be authenticated as belonging or not belonging to the dictionary. The authentication consists of a short sequence of vales that begin with an element and a sequence of values that, when hashed in order using a cryptographic associative hash function, create the same value as the hashed digest of the entire dictionary. Rather than hashing up a dynamic 2-3 tree, hashes are created in a skip list. Validation of the result of the authenticating step is provided if the hash of the short sequence matches a signed hash of the entire skip list.

The invention belongs to the field of data processing for large graphs and relates to a generation and search method for reachability chain list of a directed graph in the parallel environment. The method includes distributing the directed graph to every processor which stores nodes in the graph and sub-nodes corresponding to the nodes; compressing graph data split to the processors; calculating a backbone node reachability code of a backbone graph; building a chain index; building a skip list on the chain index; allowing data communication among the processors; allowing each processor to send skip list information to other processors; allowing each processor to upgrade own skip list information; and building a reachability index of a total graph. Through use of graph reachability compression technology in the parallel environment, the size of graph data is greatly reduced, system computing load is reduced, and a system can process the graph data on a larger scale. The method has the advantages that the speed of reading data from a disk is higher, search speed is indirectly increased, accuracy of search results is guaranteed, and network communication cost and search time are reduced greatly for a parallel computing system during searching.

A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.

Embodiments of the present invention include systems and methods for representing data in a hierarchy using a deterministic skip list data structure. In embodiments, a profile or profiles may be represented using a multi-level, time-based hierarchy using a deterministic skip list data structure comprised of nodes of local data values.

The embodiment of the invention discloses a multi-keyword matching method and a device. The method comprises the following steps: preprocessing a keyword set and building a corresponding data structure; the data structure comprises a skip list, a prefix list, a sub-skip list and a prefix length list; searching the skip list according to the content to be matched; when the skip value is zero, according to the prefix list item, calling the sub-skip list and the prefix length list to match contents to be matched. By adopting the embodiment of the invention, the skip capability of the prior art is effectively improved, the matching speed for a plurality of keywords with the same prefixes in an exact match is increased, and the efficiency of the pattern matching algorithm is greatly enhanced.

Embodiments of the present invention provide a disk data read-write method and system. The method comprises: receiving a read-write request, determining, according to the read-write request, disk data that needs to be read and written, and calculating a keyword in the disk data according to a preset hash algorithm, to obtain a hash value; searching a skip list for a storage node of the disk data in a cache according to the hash value; if the read-write request is a read request, reading the disk data from the storage node in the cache; and if the read-write request is a write request, storing the disk data into the storage node in the cache, and when a size of cache data, which is not written into a disk, in the cache is greater than a preset threshold value, writing all the cache data, which is not written into the disk, in the cache into the disk. Read and write times of the disk are effectively reduced, and a problem that an IO throughput capacity of the disk is low is resolved. Further, for a client, a problem of poor throughput capacity experience of the client is also improved efficiently.

The invention provides a message forwarding method and a device for a VXLAN gateway. According to the technical scheme of the invention, when a web board receives a data message sent from an interface board, the web board searches an ARP table item matched with the IP address of the inner-layer category of the data message. Based on a next skip-list item index matched with a next skip-list item in the ARP table item, an output interface of the matched next skip-list item is determined as an aggregation group ID. Based on the aggregation group ID, the table items of the aggregation group are matched, and one member port is selected among all matched table items of the aggregation group. According to the selected member port, the data message is sent out. Therefore, the data message can be uniformly shared and forwarded by different interface boards. Interface boards for forwarding the data message are correctly determined. The traffic congestion problem of the web board due to the uncertainty of finally selected interface boards in the prior art can be avoided.

Efficient and scalable source routed forwarding can be achieved in multi-domain networks by substituting path identifiers for intra-domain hop lists in source route hop lists. The path identifiers are then replaced with the corresponding intra-domain hop lists at the ingress edge nodes of each corresponding domain. The path identifiers do not specify individual hops along an intra-domain path segment, and are therefore typically shorter than the intra-domain hop lists. To facilitate multi-domain source routed forwarding techniques, routing tables in edge nodes of the corresponding domains are updated to associate the path identifiers with the corresponding intra-domain hop lists during (or immediately following) inter-domain path computation.

A method to produce a reverse skip list data structure in a computer readable medium, comprising: inputting streamed data to packets created in a temporary memory so as to create a sequence of packets; upon completion of creation of a packet in the stream, transferring the completed packet from the temporary memory to persistent memory; providing each of a plurality of respective packets with a respective pointer that skips over at least one other packet in the packet sequence and that indicates a location in persistent memory of a different respective packet in the packet sequence that was transferred to persistent memory prior to such providing of the respective pointer.

One embodiment of the present invention provides a system that supports concurrent accesses to a skip list that is lock-free, which means that the skip list can be simultaneously accessed by multiple processes without requiring the processes to perform locking operations. During a node deletion operation, the system receives reference to a target node to be deleted from the skip list. The system marks a next pointer in the target node to indicate that the target node is deleted, wherein next pointer contains the address of an immediately following node in the skip list. This marking operation does not destroy the address of the immediately following node, and furthermore, the marking operation is performed atomically and thereby without interference from other processes. The system then atomically modifies the next pointer of an immediately preceding node in the skip list to point to an immediately following node in the skip list, instead of pointing to the target node, thereby splicing the target node out of the skip list.

Method for the dynamic secure management of an authenticated relational table forming part of a database; the method comprises the following steps: store the authenticated relational table in a secondary memory’ with a high storage capacity and a slow data access time; maintain an authenticated skip list within the authenticated relational table in order to create an authentication superstructure; determine a signed hash or basis value which characterises the entire authenticated relational table; authenticate the presence or otherwise of a set of elements belonging to the skip list via a root path suitable for calculating a check hash value comparable to the signed hash value which characterises the entire authenticated relational table; and validate the result of the authentication step by checking that the check hash value calculated by means of the root path is equal to the signed hash value that characterises the entire authenticated relational table.

A directory structure for a sparsely filled data container comprises a linked list, doubly linked list, skip list, or other non-fully populated list technique. One or more hierarchical levels of such lists may be used for sparsely filled directories. The directory structure may be converted to a conventional look-up table directory by reconstructing the directory when the directory becomes populated to certain point.

The invention provides a message processing control method and a corresponding device. The message processing control method and the corresponding device are applied to network equipment. The network equipment comprises a downstream port and an upstream port which face a user main machine. A virtual local area network (VLAN) filter function of the downstream port is arranged to be closed. The message processing control method includes the following steps. Firstly, the downstream port is used for receiving an address resolution protocol (APR) message from the user main machine and APR study is performed on the APR message. A user VLAN identity carried by the message is stored in an APR list item. Secondly, when a next skip list item of the user main machine is added, the stored user VLAN identity in the APR list item corresponding to the user main machine is added to a corresponding next skip list item. The message processing control method and the corresponding device provide a quite simple QinQ finalization processing mechanism, a converging exchanging machine with a QinQ function is achieved and low in cost, high in reliability and free of user deployment. Meanwhile, a user network can freely project own C-VLAN and VLAN sources are multiplexed to the outmost.

An apparatus and a method for the implementation of a skip-list based cache is shown. While the traditional cache is basically a fixed length line based or fixed size block based structure, resulting in several performance problems for certain application, the skip-list based cache provides for a variable size line or block that enables a higher level of flexibility in the cache usage.

An efficient and practical method for dynamically maintaining an authenticated dictionary uses a skip list data structure and communicative hash functions to provide a dictionary database (201) that stores information objects so that any individual object can be authenticated as belonging or not belonging to the dictionary. The authentication consists of a short sequence of vales that begin with an element and a sequence of values that, when hashed in order using a cryptographic associative hash function, create the same value as the hashed digest of the entire dictionary. Rather than hashing up a dynamic 2-3 tree, hashes are created in a skip list. Validation of the result of the authenticating step is provided if the hash of the short sequence matches a signed hash of the entire skip list.

The invention provides a search process device and a network system, wherein the search process device comprises a first work mode and a second work mode; under the first work mode, a first request process unit parses a search request to obtain an IP address; a second request process unit obtains a matching index of the next skip list from the route table data according to the IP address; a first result process unit encapsulates the index of the next skip list to a data access request and send it through an interface unit; under the second work mode, the first request process unit parses the data access request to obtain the index of the next skip list; the second request process unit obtains the next skip information from the next skip list according to the index of the nest skip list; the first result process unit sends the next skip list information obtained by the second request process unit through the interface unit, so as to be perform route calculation by the network processor. The invention simplifies the route search process of the network processor, improves the system throughout rate and reduces the hardware cost and power consumption.

The invention discloses a big data indexing method and system and relates to the technical field of database index. The method comprises the following steps of: sending data generated by all terminal devices connected with a data center server unit into an NoSQL (Not Only Structured Query Language) database unit; establishing a pLSM (physical Log-Structured Merge) indexing engine unit; and carrying out indexing operation by a user. The system comprises the data center server unit, the NoSQL database unit and the pLSM indexing engine unit, wherein the data center server unit is used for receiving the data generated by all the connected terminal devices and sending the data into the NoSQL database unit; the NoSQL database unit is used for storing the data sent by the data center server unit; and the pLSM indexing engine unit is used for taking a COLA (Cache-Oblivious Lookahead Array) as an external storage assembly, taking a Skip List as an internal storage assembly and additionally arranging Delete Filter modules in an internal storage to support delete operation on the external storage assembly.

A patrol robot simultaneous localization and mapping (SLAM) method in an underground space based on a depth-inertial odometer. The method comprises loosely coupling a depth camera and an inertial measurement unit, acquiring point cloud information through a depth map acquired by the depth camera, and extracting a plane feature; converting an RGB image acquired by the depth camera into a grayscalemap to be fused with the plane feature, using an iterative closest point algorithm for optimization; loosely coupling the data subjected to the iterative closest point optimization and the data of theinertial measurement unit, using loop detection to improve the accuracy of a pose image and to obtain the trajectories of the patrol robot, a point cloud map, and a tree skip list map so as to achieve an indoor SLAM effect of the patrol robot. The method improves the simultaneous localization accuracy and robustness of the patrol robot in the underground space, and has a SLAM effect of the patrolrobot in the underground space. When the patrol robot operates in the underground space, the method has good robustness under a strong rotating environment.

A compiler and method of compiling provide enhanced performance by utilizing a skip list data structure to store various properties of a program at points of interest in the procedure, for example, the properties of the statements in each block in the control flow graph. A special procedure is used to initialize the skip list, prior to performing data flow analysis, to ensure that the skip list structure is not used in an inefficient manner as a result of initialization. Furthermore, special procedures are used to simultaneously scan and compare two skip lists as part of solving dataflow equations.

The invention discloses a skip list based cross-site scripting attack defense method, and aims at detecting cross-site scripting attack vulnerability. The method comprises the steps of reading attack code field value of a cross-site scripting (XSS) attack XSS sample; standardizing; performing MD5 coding and integer conversion to obtain the long integer type data of the sample; creating skip list nodes to form a skip list which forms an attack vector feature database; intercepting data information submitted through POST / GET manner based on the HTTP traffic packet analysis; extracting the scrip vector parameter set according to the request header key value; standardizing; generating all sub-sequence sets A of which threshold values are possibly specified to the length L by the DFA description manner; performing 16-bit MD5 coding and integer conversion for each sub-sequence in A to obtain the long integer type; matching the long integer type of A with the skip list nodes in the feature database; if matching, performing dirt marking for script parameter Sm to obtain the vulnerability detection result.

The invention discloses a request processing method for a storage system by using a mixed memory key value, which comprises the following steps of: if a point query request is obtained, searching a hash table and returning a query result; If the skip list is the range query request, constructing a corresponding skip list command, adding the skip list command to a command cache queue of each skip list, waiting until return results of all skip lists are obtained, combining the obtained return results according to the lexical order, and returning the combined return results; If the request is thewrite request, distributing a memory in the NVM and writing a value; Further judging the type of the write request, if the write request is an update request, updating the hash table, and constructing a corresponding table skip command; If the request is the insertion request, newly establishing a skip list node, updating a hash table, and constructing a corresponding skip list command; And determining a target skip list according to the length of the key in the write request, and adding a skip list command to a command cache queue of the target skip list. According to the method, the read-write delay of the medium is fully considered, and the processing performance of the read operation with high proportion is optimized, so that the overall performance of the system is effectively improved.

To facilitate programming a TV channel list, only digital channels are presented on an edit list so that the user need not parse through analog channels but only the digital channels to edit the channels (e.g., by putting the channels on a favorite list, or a skip list, or by labelling the channels, etc.).

A method and system for managing a plurality of defects that may cause an error during a write operation in a write-once data storage disk is provided. A host system sends a write command to a disk drive that contains the storage disk. The process detects any errors that may occur during the write operation. When an error is detected, a “skip list” containing the addresses of physical sectors on the disk that are to be skipped during a read operation is updated, the write operation is suspended, and the process attempts to rewrite the data in another sector. If the rewrite is performed successfully, the write operation continues. Otherwise, the write operation is terminated and the host device is notified. While the disk drive is operative, the skip list is preferably maintained in a buffer memory, but periodically the entries in the skip list are copied to the disk for permanent storage. Before a read operation begins, the skip list is copied from the disk to the memory. When a file is read from the disk, any “skip sectors” that are encompassed within the file are skipped (i.e., the data in those sectors is not read). The method of this invention is particularly useful in supplementing an error correction code, which typically has difficulty dealing with errors of longer duration.

The invention discloses an index structure based on a dictionary tree, a data query optimization method and a main memory manager, and belongs to the field of data storage. The index structure is composed of containers, wherein the containers store T nodes and S nodes; complete keys are divided into partial keys; the T nodes store the front m / 2 bits of the partial keys, and the S nodes store the rear m / 2 bits of the partial keys; and the partial keys passing through a certain node path from the root node of the dictionary tree are connected to form the complete keys. And the index structure ismore compact, so that the main memory space utilization rate is improved. The T node is directly skipped to a subsequent brother node by using a skipping relay, so that the comparison frequency is reduced, and the search performance is improved; a T node skip list is used for skipping a T node to an S node, a container skip list is used for skipping the S node to the T node, and the S node directly skips to the nearest target, so that a large number of unnecessary entries are skipped, and the searching performance is improved; and the index structure and the main memory address are completelydecoupled by a pointer P which is analyzed by the main memory manager and contains each hierarchical structure ID.

The invention provides a multimode searching method and a system. The system comprises a first processing unit, a first memory cell and a second processing unit. The first processing unit establishes a keyword tree according to word serials of a plurality of modes, and creates a skip list aiming at each node in the keyword tree, the skip list includes a plurality of index terms and a plurality of identification serial numbers corresponding to the index terms, and the identification serial numbers, which are positioned at the aimed node and take the index terms are the indexes, are the identification serial numbers of the next node which should enters. The second processing unit checks whether a word serial contains one of the word serials of the the modes according to the skip lists of all the nodes stored in the first memory unit. The invention uses the second processing unit and the skip list to execute searching, so the performance of the entire system can be improved.

The application provides the embodiment of a method for interface interaction. The method of the embodiment can respond to a skip operation triggered by a user on a current subpage of a browser; an opened web page corresponding to the skip operation is searched among multiple stored opened web pages which are once opened by the user; a corresponding web page index is generated for the found opened web page; and the web page index can then be displayed on the current subpage in the form of a skip list, so that the user can select a certain web page index in the skip list so as to response to the user's selection of the web page index. According to the embodiment, the browser is triggered to skip to a target web page denoted by the target web page index from the current subpage. Obviously, the method provided by the embodiment has the advantages that the user who browses the web page in the form of the subpage can very easily skip the current subpage to the web page which is once browsed according to browsing history; the skip mode is simple and convenient; and experience of the user is good. In addition, the application also provides the embodiment of a device for the interface interaction, wherein the device is used to ensure application and achievement of the method in practice.

A disc player for playing files recorded on discs includes a skip list storage section, a registration section and a controller. The skip list storage section stores a skip list which includes information on a skip file which does not have to be played among files recorded on a mounted disc. The registration section selects the skip file from a recorded file list which includes information on files recorded on the mounted disc and registers the skip file to the skip list stored by the skip list storage section. The controller plays the files recorded on the mounted disc excepting the skip file. The skip list is deleted when the mounted disc is ejected.