CN110704419A - Data structure, data indexing method, device and equipment, and storage medium - Google Patents
Data structure, data indexing method, device and equipment, and storage medium Download PDFInfo
- Publication number
- CN110704419A CN110704419A CN201810644706.XA CN201810644706A CN110704419A CN 110704419 A CN110704419 A CN 110704419A CN 201810644706 A CN201810644706 A CN 201810644706A CN 110704419 A CN110704419 A CN 110704419A
- Authority
- CN
- China
- Prior art keywords
- data
- bloom filter
- mapping
- positioning array
- data structure
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
- 238000000034 method Methods 0.000 title claims abstract description 34
- 238000013507 mapping Methods 0.000 claims abstract description 84
- 238000007906 compression Methods 0.000 claims abstract description 21
- 230000006835 compression Effects 0.000 claims abstract description 21
- 230000006870 function Effects 0.000 description 11
- 230000006854 communication Effects 0.000 description 6
- 238000004891 communication Methods 0.000 description 5
- 230000008569 process Effects 0.000 description 5
- 238000010586 diagram Methods 0.000 description 4
- 230000003068 static effect Effects 0.000 description 4
- 238000012545 processing Methods 0.000 description 3
- 230000005540 biological transmission Effects 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000006855 networking Effects 0.000 description 2
- 238000013144 data compression Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 238000011160 research Methods 0.000 description 1
- 230000004044 response Effects 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Databases & Information Systems (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Information Transfer Between Computers (AREA)
Abstract
The invention discloses a data structure, a data indexing method, a data indexing device, a data indexing equipment and a computer readable storage medium, wherein the data structure comprises the following components: a compressed bloom filter containing m bits and a positioning array containing j bits; the positioning array and the compressed bloom filter have a mapping relation; the compressed bloom filter is used for performing Hash mapping operation on input data and compressing the data after the Hash mapping operation; the value of the positioning array is used as an offset address of the input data in the memory for memory access. The data structure of the invention has the capability of transmitting and sharing the represented information in the network, can realize the direct index of the data, has high data index efficiency, can be directly deployed in an on-chip high-speed memory, and effectively realizes the storage compression of the index structure.
Description
Technical Field
The present invention relates to the field of communications technologies, and in particular, to a data structure, a data indexing method, an apparatus, and a computer-readable storage medium.
Background
To implement content-oriented communication, information-centric networks employ content-requestor-driven communication modes. Two types of data packets are used in the communication process: an Interest package and a Data package. Meanwhile, 3 data structures are deployed in the forwarding plane: the CS (Content Store, Content storage pool), the PIT (Pending Interest Table), and the FIB (Forwarding Information Base) implement fast retrieval, intelligent Forwarding, and high-efficiency Content caching of the data packet on the Forwarding plane. In the forwarding plane, when a plurality of Interest packets simultaneously request the same data, the forwarding plane only forwards the first received Interest packet, and stores the requests in the PIT. When the Data packet is returned along the reverse path of the Interest packet, the forwarding plane only finds the matched entry in the PIT, and forwards the Data packet to the interfaces respectively according to the interface list displayed in the entry. After the forwarding is completed, the corresponding PIT entry is deleted and the Data packet is stored in the CS.
The communication mode in which the information center network processes each packet puts high demands on the performance of the forwarding plane, particularly the storage capacity of the router and the processing speed of the packet. For example, when information of a plurality of Interest packets is stored in the PIT table of the forwarding plane, each of the Interest packets corresponds to one communication request, and the information is stored in the PIT table until a Data packet in response is returned, so that the amount of Data in the PIT table is very large. Studies have shown that in the PIT table of a router forwarding plane, the order of record entries can be expressed as: bandwidth RTT/P. Where P represents the average size of the Data packets, and RTT represents the average waiting time of Interest recorded in the PIT table. For a 10Gbps link, if a router contains 10 ports, the time is 100ms, and the average size P of Data packets is 1000Bytes, the PIT table of the router will contain at least 1000,000,000 records. Although current routers based on TCP/IP technology can support millions of records, the content of each record in the PIT table is much more complex than the records of the IP routing table. In addition, as network link speeds increase and the number of routing ports increases, the size of the forwarding plane PIT table will also grow by orders of magnitude. Therefore, how to further improve the storage capacity of the router, accelerate the retrieval speed of the data, and realize the routing data sharing at the same time becomes a hot research problem of the forwarding plane of the information center network.
Disclosure of Invention
In view of this, embodiments of the present invention provide a data structure, a data indexing method, a data indexing device, a data indexing apparatus, and a computer-readable storage medium, so as to solve the performance problem of the forwarding plane of the information-centric network.
The technical scheme adopted by the embodiment of the invention for solving the technical problems is as follows:
according to an aspect of an embodiment of the present invention, there is provided a data structure, including: a compressed bloom filter containing m bits and a positioning array containing j bits, where m > j; the positioning array and the compressed bloom filter have a mapping relation;
the compressed bloom filter is used for performing Hash mapping operation on input data and compressing the data after the Hash mapping operation;
the value of the positioning array is used as an offset address of the input data in the memory for memory access.
According to another aspect of the embodiments of the present invention, there is provided a data indexing method, including the steps of:
performing hash mapping operation on input data for k times in the compressed bloom filter, and compressing the data after the hash mapping operation for k times;
if the input data has Hash mapping in the ith part of the compressed bloom filter, setting the value of the ith bit of the positioning array as a first binary base number, wherein i is not more than j;
and finally obtaining the numerical value of the positioning array as the offset address of the input data in the memory for memory access.
According to another aspect of the embodiments of the present invention, there is provided a data indexing apparatus, including a hash mapping operation module and a spatial address mapping module;
the Hash mapping operation module is used for performing Hash mapping operation on input data for k times in the compressed bloom filter and compressing the data after the Hash mapping operation for k times;
the spatial address mapping module is configured to set a value of an ith bit of the positioning array as a first binary base if the input data has hash mapping in an ith part of the compressed bloom filter, where i is not greater than j; and finally obtaining the numerical value of the positioning array as the offset address of the input data in the memory for memory access.
According to another aspect of the embodiments of the present invention, there is provided a data indexing apparatus, the apparatus including: the data indexing system comprises a memory, a processor and a data indexing program which is stored on the memory and can run on the processor, wherein the data indexing program realizes the steps of the data indexing method when being executed by the processor.
According to another aspect of the embodiments of the present invention, there is provided a computer-readable storage medium having stored thereon a data indexing program, which when executed by a processor, implements the steps of the data indexing method described above.
The data structure, the data indexing method, the data indexing device, the data indexing equipment and the computer readable storage medium have the advantages that the data structure has the capability of transmitting and sharing the represented information in a network, the direct indexing of data can be realized, the data indexing efficiency is high, the data indexing device can be directly deployed in an on-chip high-speed memory, and the storage compression of the index structure is effectively realized.
Drawings
FIG. 1 is a diagram illustrating a data structure according to a first embodiment of the present invention;
FIG. 2 is a diagram illustrating a data indexing process according to a second embodiment of the present invention;
FIG. 3 is another flow chart illustrating data indexing according to a second embodiment of the present invention;
FIG. 4 is a schematic structural diagram of a data indexing device according to a third embodiment of the present invention;
FIG. 5 is a schematic view of another structure of a data indexing device according to a third embodiment of the present invention;
FIG. 6 is a diagram illustrating a data indexing apparatus according to a fourth embodiment of the present invention.
The implementation, functional features and advantages of the objects of the present invention will be further explained with reference to the accompanying drawings.
Detailed Description
In order to make the technical problems, technical solutions and advantageous effects to be solved by the present invention clearer and clearer, the present invention is further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are merely illustrative of the invention and are not intended to limit the invention.
First embodiment
As shown in fig. 1, a first embodiment of the present invention provides a data structure including: a Compressed Bloom filter 10(Compressed Bloom filter) containing m bits and a positioning Array 20(Mapping Array, MA for short) containing j bits, where m > j; the positioning array 20 has a mapping relation with the compressed bloom filter 10;
the compressed bloom filter 10 is configured to perform a hash mapping operation on input data, and compress data after the hash mapping operation.
In the present embodiment, the compressed bloom filter 10 includes a bloom filter 11 and a compression unit 12;
the bloom filter 11 is configured to perform a hash mapping operation on the input data;
the compressing unit 12 is configured to compress the data subjected to the hash mapping operation by the bloom filter 11.
The value of the positioning array 20 is used as an offset address of the input data in memory for memory access.
In this embodiment, the compression unit 12 is equally divided into j parts, and each part corresponds to one bit of the positioning array 20.
As an example, please refer to fig. 1, it is assumed that the location array 20 is an array having 6 bits, the compression unit 12 is set to 18 bits, and the compression unit 12 is equally divided into 6 parts, each of which corresponds to one bit of the location array 20, for example, 123 of the compression unit 12 is the 1st part (shown in fig. 1 st) and corresponds to the first bit of the location array 20 (shown in fig. 1 st).
In this embodiment, the data structure may represent a set S of n elements, where S ═ x1,x2,x3,...,xnThe basic function of element retrieval, i.e. determining whether a data element is in the set S represented by the data structure, can be implemented. Meanwhile, the data compression function of the data structure can effectively reduce the data transmission amount in the network; the data structure has the functions of network data transmission and data sharing by transmitting the bit array of the data structure in the network. For each data element x that operates on the data structure, the positioning array 20 will determine the k hash-mapped values h of the element x in the compressed bloom filter 10i(x),i∈[1,k]Then, a value M (x) e [0, j-1 ] is mapped again]. If the element x ∈ S, i.e., x exists in the set S represented by the data structure, then the value m (x) of the location array 20 will be used for a store access as the actual offset address of the element in memory.
The data structure of the embodiment of the invention has the capability of transmitting and sharing the represented information in the network, can realize direct indexing of data, has high data indexing efficiency, can be directly deployed in an on-chip high-speed memory, and effectively realizes storage compression of the index structure.
Second embodiment
As shown in fig. 2, a second embodiment of the present invention provides a method for indexing data in the data structure according to the first embodiment, the method comprising the steps of:
s21, performing k hash mapping operations on the input data in the compressed bloom filter, and compressing the data after the k hash mapping operations.
In this embodiment, the input data may be variable-length string data, such as variable-length string name data, and is not particularly limited herein.
S22, if the input data has hash mapping in the ith part of the compressed bloom filter, setting the value of the ith bit of the positioning array as a first binary base, wherein i is less than or equal to j.
S23, using the finally obtained value of the positioning array as the offset address of the input data in the memory for memory access.
Referring to fig. 3, in an embodiment, before performing k hash mapping operations on input data in a compressed bloom filter and compressing data after the k hash mapping operations, the method further includes the following steps:
s20, each bit of the positioning array is initialized to be a second binary base number.
In this embodiment, the first binary base may be 0 or 1; the second binary base may also be 0 or 1.
By way of example, assuming that the data structure uses a K-3 hash function, the bloom filter is sized to 32 bits, the compression unit is sized to 18 bits, the positioning array is a 6-bit array, and the data structure may index 2 in the static physical storage unit6And (4) each element. The three elements X, Y, Z are entered sequentially, and the orientation array is initialized to the all 0 state each time before the elements are entered. When X is input, bits 1, 6, and 11 in the bloom filter are hashed, and all three bits are 1, i.e., element X is present in the data structure. Through compressed sensing, hash mapping exists in the 1st, 2 nd and 3 th parts of the compression unit, so that the value of the 1st, 2 nd and 3 rd bit of the positioning array is set to be 1, and the value of the other positions is 0. The resulting value of the location array is 111000, i.e., the offset address of the X element in the static physical memory location is 111000. Similarly, elements Y and Z are also present in the data structure, with offset addresses: 010101 and 100011.
In the embodiment, the misjudgment probability is a key performance for describing the data structure, and the misjudgment of the data structure can be defined asThe data structure erroneously determines that an element not belonging to the set S exists in the set S or a mapping conflict occurs when a spatial address mapping is performed on a certain element. Assuming that all hash functions used by the compressed bloom filter are random, uniform and independent of each other, the probability P of misjudgment of the data structure occursCoMBF＝Pcbf+PMA-P(cbf∩MA)In which P iscbfProbability of erroneous judgment for said compressed bloom filter, PMAFor the probability of a mapping conflict when mapping spatial addresses in the positioning array, P(cbf∩MA)The probability of a mapping conflict occurring when a false positive occurs for the compressed bloom filter and a spatial address mapping is performed in the positioning array at the same time.
In this embodiment, PcbfCan be represented as Pcbf＝(1-ρ)k，
Where ρ ═ 1-1/m)knN represents the size of the set S, m represents the length of the compressed bloom filter bit array, and k represents the number of hash functions used in the data structure.
In this embodiment, PMACan be expressed asWhere j represents the size of the positioning array.
In this embodiment, P(cbf∩MA)Can be expressed as
Therefore, the probability of a false positive for a data structure can be expressed as:
in conclusion, the data structure has the capacity of transmitting and sharing the represented information in the network, and meanwhile, the hash mapping process of the name data in the compressed bloom filter skillfully solves the problem of processing the name data of the variable-length character string. For each visitWhen the name data of the data structure is inquired, the direct index of the data can be realized only by mapping k hash functions in the chip once. Therefore, the data indexing efficiency of the data structure is far better than the data indexing mode of combining the bloom filter and the hash table. In addition, the storage space occupied by the data structure is (m + j) bits, and the number of the indexable data contents can be expressed as:
when the data structure is applied to a content-oriented information-centric networking data plane, its storage capacity requirement should be about: 2MB to 3 MB. Namely, the data structure can be directly deployed in the on-chip high-speed memory, and the storage compression of the index structure is effectively realized.
According to the data indexing method provided by the embodiment of the invention, the data structure has the capability of transmitting and sharing the represented information in the network, can be directly deployed in the on-chip high-speed memory, and effectively realizes the storage compression of the index structure; the direct indexing of the data is realized, and the data indexing efficiency is high.
Third embodiment
As shown in fig. 4, a third embodiment of the present invention provides a data indexing apparatus, which includes a hash mapping operation module 31 and a spatial address mapping module 32;
the hash mapping operation module 31 is configured to perform hash mapping operations on input data k times in the compressed bloom filter, and compress data after the hash mapping operations k times;
in this embodiment, the input data may be variable-length string data, such as variable-length string name data, and is not particularly limited herein.
The spatial address mapping module 32 is configured to set a value of an ith bit of the positioning array as a first binary base if the input data has hash mapping in an ith portion of the compressed bloom filter, where i is not greater than j; and finally obtaining the numerical value of the positioning array as the offset address of the input data in the memory for memory access.
Referring to fig. 5, in one embodiment, the apparatus further includes an initialization module 30;
the initialization module 30 is configured to initialize each bit of the positioning array to a second binary radix.
In this embodiment, the first binary base may be 0 or 1; the second binary base may also be 0 or 1.
By way of example, assuming that the data structure uses a K-3 hash function, the bloom filter is sized to 32 bits, the compression unit is sized to 18 bits, the positioning array is a 6-bit array, and the data structure may index 2 in the static physical storage unit6And (4) each element. The three elements X, Y, Z are entered sequentially, and the orientation array is initialized to the all 0 state each time before the elements are entered. When X is input, bits 1, 6, and 11 in the bloom filter are hashed, and all three bits are 1, i.e., element X is present in the data structure. Through compressed sensing, hash mapping exists in the 1st, 2 nd and 3 th parts of the compression unit, so that the value of the 1st, 2 nd and 3 rd bit of the positioning array is set to be 1, and the value of the other positions is 0. The resulting value of the location array is 111000, i.e., the offset address of the X element in the static physical memory location is 111000. Similarly, elements Y and Z are also present in the data structure, with offset addresses: 010101 and 100011.
In this embodiment, the misjudgment probability is a key performance for describing the data structure, and the misjudgment of the data structure may be defined as a phenomenon that the data structure erroneously judges an element not belonging to the set S as being present in the set S, or when performing spatial address mapping on a certain element, a mapping conflict occurs. Assuming that all hash functions used by the compressed bloom filter are random, uniform and independent of each other, the probability P of misjudgment of the data structure occursCoMBF＝Pcbf+PMA-P(cbf∩MA)In which P iscbfProbability of erroneous judgment for said compressed bloom filter, PMAFor the probability of a mapping conflict when mapping spatial addresses in the positioning array, P(cbf∩M1)Misjudging the compressed bloom filter and at the same timeAnd the probability of mapping conflict when the space address mapping is carried out in the positioning array.
In this embodiment, PcbfCan be represented as Pcbf＝(1-ρ)k，
Where ρ ═ 1-1/m)knN represents the size of the set S, m represents the length of the compressed bloom filter bit array, and k represents the number of hash functions used in the data structure.
In this embodiment, PM1Can be expressed asWhere j represents the size of the positioning array.
In this embodiment, P(cbf∩M1)Can be expressed as
Therefore, the probability of a false positive for a data structure can be expressed as:
in conclusion, the data structure has the capacity of transmitting and sharing the represented information in the network, and meanwhile, the hash mapping process of the name data in the compressed bloom filter skillfully solves the problem of processing the name data of the variable-length character string. For each name data of the access data structure, direct index of the data can be realized only by mapping k hash functions in the chip once. Therefore, the data indexing efficiency of the data structure is far better than the data indexing mode of combining the bloom filter and the hash table. In addition, the storage space occupied by the data structure is (m + j) bits, and the number of the indexable data contents can be expressed as:
when the data structure is applied to a content-oriented information-centric networking data plane, its storage capacity requirement should be about: 2MB to 3 MB. That is, the data structure can be directly deployed in the on-chip high-speed storageAnd effectively realizes the storage compression of the index structure.
According to the data indexing device provided by the embodiment of the invention, the data structure has the capability of transmitting and sharing the represented information in the network, can be directly deployed in the on-chip high-speed memory, and effectively realizes the storage compression of the indexing structure; the direct indexing of the data is realized, and the data indexing efficiency is high.
Fourth embodiment
As shown in fig. 6, a fourth embodiment of the present invention provides a data indexing apparatus, including: a memory 41, a processor 42, and a data indexing program stored on the memory 41 and executable on the processor 42, wherein the data indexing program is used for implementing the following steps of the data indexing method when executed by the processor 42:
performing hash mapping operation on input data for k times in the compressed bloom filter, and compressing the data after the hash mapping operation for k times;
if the input data has Hash mapping in the ith part of the compressed bloom filter, setting the value of the ith bit of the positioning array as a first binary base number, wherein i is not more than j;
and finally obtaining the numerical value of the positioning array as the offset address of the input data in the memory for memory access.
The data indexing program, when executed by the processor 42, is further configured to implement the steps of the data indexing method as follows:
each bit of the positioning array is initialized to a second binary radix.
The data indexing program, when executed by the processor 42, is further configured to implement the steps of the data indexing method as follows:
probability P of misjudgment of data structureCoMBF＝Pcbf+PMA-P(cbf∩MA)In which P iscbfProbability of erroneous judgment for said compressed bloom filter, PMAFor the probability of a mapping conflict when mapping spatial addresses in the positioning array, P(cbf∩MA)The probability of a mapping conflict occurring when a false positive occurs for the compressed bloom filter and a spatial address mapping is performed in the positioning array at the same time.
According to the data indexing equipment disclosed by the embodiment of the invention, the data structure has the capability of transmitting and sharing the represented information in a network, can be directly deployed in an on-chip high-speed memory, and effectively realizes the storage compression of the indexing structure; the direct indexing of the data is realized, and the data indexing efficiency is high.
Fifth embodiment
A fifth embodiment of the present invention provides a computer-readable storage medium, which stores thereon a data indexing program, which when executed by a processor, is configured to implement the steps of the data indexing method according to the second embodiment.
According to the computer-readable storage medium provided by the embodiment of the invention, the data structure has the capability of transmitting and sharing the represented information in a network, can be directly deployed in an on-chip high-speed memory, and effectively realizes the storage compression of the index structure; the direct indexing of the data is realized, and the data indexing efficiency is high.
It should be noted that the device embodiment and the method embodiment belong to the same concept, and specific implementation processes thereof are described in the method embodiment in detail, and technical features in the method embodiment are correspondingly applicable in the device embodiment, which is not described herein again.
Through the above description of the embodiments, those skilled in the art will clearly understand that the method of the above embodiments can be implemented by software plus a necessary general hardware platform, and certainly can also be implemented by hardware, but in many cases, the former is a better embodiment. Based on such understanding, the technical solutions of the present invention may be embodied in the form of a software product, which is stored in a storage medium (such as ROM/RAM, magnetic disk, optical disk) and includes instructions for enabling a terminal device (such as a mobile phone, a computer, a server, an air conditioner, or a network device) to execute the method according to the embodiments of the present invention.
The preferred embodiments of the present invention have been described above with reference to the accompanying drawings, and are not to be construed as limiting the scope of the invention. Those skilled in the art can implement the invention in various modifications, such as features from one embodiment can be used in another embodiment to yield yet a further embodiment, without departing from the scope and spirit of the invention. Any modification, equivalent replacement and improvement made within the technical idea of using the present invention should be within the scope of the right of the present invention.
Claims (11)
1. A data structure, characterized in that the data structure comprises: a compressed bloom filter containing m bits and a positioning array containing j bits, where m > j; the positioning array and the compressed bloom filter have a mapping relation;
the compressed bloom filter is used for performing Hash mapping operation on input data and compressing the data after the Hash mapping operation;
the value of the positioning array is used as an offset address of the input data in the memory for memory access.
2. The data structure of claim 1, wherein the compressed bloom filter comprises a bloom filter and a compression unit;
the bloom filter is used for carrying out Hash mapping operation on the input data;
and the compression unit is used for compressing the data subjected to the hash mapping operation of the bloom filter.
3. The data structure of claim 2, wherein the compression unit is equally divided into j portions, and each portion corresponds to one bit of the positioning array.
4. A method of indexing data in a data structure according to any one of claims 1 to 3, the method comprising the steps of:
performing hash mapping operation on input data for k times in the compressed bloom filter, and compressing the data after the hash mapping operation for k times;
if the input data has Hash mapping in the ith part of the compressed bloom filter, setting the value of the ith bit of the positioning array as a first binary base number, wherein i is not more than j;
and finally obtaining the numerical value of the positioning array as the offset address of the input data in the memory for memory access.
5. The method of claim 4, wherein before performing k hash mapping operations on the input data in the compressed bloom filter and compressing the data after the k hash mapping operations, the method further comprises:
each bit of the positioning array is initialized to a second binary radix.
6. The method of claim 4, wherein the probability P of the data structure being misjudgedCoMBF＝Pcbf+PM1-P(cbf∩MA)In which P iscbfProbability of erroneous judgment for said compressed bloom filter, PMAFor the probability of a mapping conflict when mapping spatial addresses in the positioning array, P(cbf∩MA)The probability of a mapping conflict occurring when a false positive occurs for the compressed bloom filter and a spatial address mapping is performed in the positioning array at the same time.
7. A data indexing device is characterized by comprising a hash mapping operation module and a space address mapping module;
the Hash mapping operation module is used for performing Hash mapping operation on input data for k times in the compressed bloom filter and compressing the data after the Hash mapping operation for k times;
the spatial address mapping module is configured to set a value of an ith bit of the positioning array as a first binary base if the input data has hash mapping in an ith part of the compressed bloom filter, where i is not greater than j; and finally obtaining the numerical value of the positioning array as the offset address of the input data in the memory for memory access.
8. The apparatus of claim 7, further comprising an initialization module;
the initialization module is used for initializing each bit of the positioning array into a second binary base number.
9. The apparatus of claim 7, wherein the probability P that the data structure is misjudgedCoMBF＝Pcbf+PMA-P(cbf∩MA)In which P iscbfProbability of erroneous judgment for said compressed bloom filter, PMAFor the probability of a mapping conflict when mapping spatial addresses in the positioning array, P(cbf∩MA)The probability of a mapping conflict occurring when a false positive occurs for the compressed bloom filter and a spatial address mapping is performed in the positioning array at the same time.
10. A data indexing device, characterized in that the device comprises: memory, a processor and a data indexing program stored on the memory and executable on the processor, the data indexing program when executed by the processor implementing the steps of the data indexing method as claimed in any one of claims 4 to 6.
11. A computer-readable storage medium, having stored thereon a data indexing program which, when executed by a processor, implements the steps of the data indexing method of any one of claims 4 to 6.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810644706.XA CN110704419A (en) | 2018-06-21 | 2018-06-21 | Data structure, data indexing method, device and equipment, and storage medium |
| PCT/CN2019/081205 WO2019242374A1 (en) | 2018-06-21 | 2019-04-03 | Data structure, data indexing method, apparatus, and device, and storage medium |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810644706.XA CN110704419A (en) | 2018-06-21 | 2018-06-21 | Data structure, data indexing method, device and equipment, and storage medium |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN110704419A true CN110704419A (en) | 2020-01-17 |
Family
ID=68983237
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810644706.XA Withdrawn CN110704419A (en) | 2018-06-21 | 2018-06-21 | Data structure, data indexing method, device and equipment, and storage medium |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN110704419A (en) |
| WO (1) | WO2019242374A1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113329048A (en) * | 2021-04-13 | 2021-08-31 | 网络通信与安全紫金山实验室 | Cloud load balancing method and device based on switch and storage medium |
| CN115422142A (en) * | 2022-08-22 | 2022-12-02 | 北京羽乐创新科技有限公司 | Data compression method and device |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103729307A (en) * | 2012-10-15 | 2014-04-16 | 三星电子株式会社 | Data compression apparatus and method and memory system comprising data compression apparatus |
| CN105530328A (en) * | 2014-10-17 | 2016-04-27 | 思科技术公司 | Address autoconfiguration using bloom filter parameters for unique address computation |
| CN105989061A (en) * | 2015-02-09 | 2016-10-05 | 中国科学院信息工程研究所 | Rapid indexing method for repeated detection of multi-dimensional data under sliding window |
| CN107908357A (en) * | 2017-10-13 | 2018-04-13 | 天津大学 | Name data network Forwarding plane PIT storage organizations and its data retrieval method |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104408069A (en) * | 2014-10-30 | 2015-03-11 | 浪潮电子信息产业股份有限公司 | Consistency content design method based on Bloom filter thought |
| CA2876466C (en) * | 2014-12-29 | 2022-07-05 | Ibm Canada Limited - Ibm Canada Limitee | Scan optimization using bloom filter synopsis |
| CN107832343B (en) * | 2017-10-13 | 2020-02-21 | 天津大学 | A method for fast data retrieval based on bitmap-based MBF data index structure |
-
2018
- 2018-06-21 CN CN201810644706.XA patent/CN110704419A/en not_active Withdrawn
-
2019
- 2019-04-03 WO PCT/CN2019/081205 patent/WO2019242374A1/en active Application Filing
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103729307A (en) * | 2012-10-15 | 2014-04-16 | 三星电子株式会社 | Data compression apparatus and method and memory system comprising data compression apparatus |
| CN105530328A (en) * | 2014-10-17 | 2016-04-27 | 思科技术公司 | Address autoconfiguration using bloom filter parameters for unique address computation |
| CN105989061A (en) * | 2015-02-09 | 2016-10-05 | 中国科学院信息工程研究所 | Rapid indexing method for repeated detection of multi-dimensional data under sliding window |
| CN107908357A (en) * | 2017-10-13 | 2018-04-13 | 天津大学 | Name data network Forwarding plane PIT storage organizations and its data retrieval method |
Non-Patent Citations (2)
| Title |
|---|
| 王鹏;: "关于布隆过滤器在BSS中应用", 中国新通信, no. 01, 5 January 2017 (2017-01-05) * |
| 饶文;陈旭;: "基于布隆过滤器的海量数据查询技术的优化与应用", 微型电脑应用, no. 02, 20 February 2018 (2018-02-20) * |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113329048A (en) * | 2021-04-13 | 2021-08-31 | 网络通信与安全紫金山实验室 | Cloud load balancing method and device based on switch and storage medium |
| CN115422142A (en) * | 2022-08-22 | 2022-12-02 | 北京羽乐创新科技有限公司 | Data compression method and device |
Also Published As
| Publication number | Publication date |
|---|---|
| WO2019242374A1 (en) | 2019-12-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP2314027B1 (en) | Switching table in an ethernet bridge | |
| US9253091B2 (en) | Method for processing a request in an information-centric communication network | |
| CN110166570B (en) | Service session management method and device, and electronic device | |
| CN101594319B (en) | Entry lookup method and entry lookup device | |
| CN102971732A (en) | System architecture for integrated hierarchical query processing for key/value stores | |
| US11310158B2 (en) | Packet classification using fingerprint hash table | |
| JPH077524A (en) | How to access the communication subscriber's address identifier | |
| EP3657740A1 (en) | Message forwarding | |
| CN114039875A (en) | Data acquisition method, device and system based on eBPF technology | |
| US10790862B2 (en) | Cache index mapping | |
| CN106294191B (en) | The method for handling table, the method and apparatus for accessing table | |
| CN103795815A (en) | Network communication system and network communication method | |
| CN110704419A (en) | Data structure, data indexing method, device and equipment, and storage medium | |
| CN101599910A (en) | The method and apparatus that message sends | |
| CN105939397A (en) | Message transmission method and device | |
| US11489765B2 (en) | Data processing method and device, and computer readable storage medium | |
| US9667540B2 (en) | Fiber channel over ethernet (FCoE) frame forwarding system | |
| CN114265869B (en) | Data message forwarding method and device, storage medium and electronic device | |
| CN104994186A (en) | Query method, processor and device of media access control address | |
| CN117640513A (en) | Data processing method, device and system | |
| CN111131197B (en) | Filtering strategy management system and method thereof | |
| CN113259271A (en) | Message switching method and message switching system | |
| CN119232668B (en) | Fragment message tuple recovery method, network card, gateway, storage medium and program | |
| CN106302174A (en) | A kind of method and device realizing route querying | |
| KR102562765B1 (en) | IP Band Information Extraction System And Method Thereof |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| WW01 | Invention patent application withdrawn after publication | ||
| WW01 | Invention patent application withdrawn after publication |
Application publication date: 20200117 |