Search device and search method searching data based on key
According to one embodiment, a search device includes a first comparison module, a determination module, a correction module, a second comparison module, and a search module. The first comparison module compares a received first key with a second key read from a nonvolatile memory. The determination module determines whether error correction is possible based on a first comparison result obtained by the first comparison module. The correction module generates a third key by applying an error correction process to the second key if the determination module determines that error correction is possible. The second comparison module compares the first key with the third key. The search module reads data associated with the second key in the nonvolatile memory if a second comparison result obtained by the second comparison module shows a match.
1. A search device comprising:
a first comparison unit which compares a received first key with a second key read from a nonvolatile memory;
a determination unit which determines, based on a first comparison result obtained by the first comparison unit, whether or not a difference between the first key and the second key is within a range of an error correction capability of an error correction process;
a correction unit which generates a third key by applying the error correction process to the second key if the determination unit determines that the difference is within the range;
a second comparison unit which compares the first key with the third key; and
a search unit which reads data associated with the second key in the nonvolatile memory if a second comparison result obtained by the second comparison unit shows a match.
2. The search device of claim 1 , wherein
the first comparison unit compares the first key with a next second key read from the nonvolatile memory if the determination unit determines that the difference is not within the range or if the second comparison result shows a mismatch,
the determination unit determines, based on a comparison result between the first key and the next second key, whether or not a difference between the first key and the next second key is within the range,
the correction unit generates a next third key by applying the error correction process to the next second key if the determination unit determines that the difference between the first key and the next second key is within the range,
the second comparison unit compares the first key with the next third key, and
the search unit reads data associated with the next second key in the nonvolatile memory if the first key matches the next third key.
3. The search device of claim 1 , wherein
the first comparison unit calculates a Hamming distance based on the first key and the second key, and
the determination unit determines whether the Hamming distance is within the range.
4. The search device of claim 1 , further comprising
a transmission unit which transmits a signal indicating that data corresponding to the first key is not present in the nonvolatile memory to an information processing device, if all of candidate keys corresponding to the first key have been read from the nonvolatile memory and the data corresponding to the first key is not read.
5. The search device of claim 1 , wherein the correction unit corrects an error of the data read by the search unit.
6. The search device of claim 1 , wherein the correction unit corrects an error of the second key based on an error correcting code (ECC).
7. The search device of claim 1 , wherein the first comparison unit is provided in a memory controller which controls writing and reading relative to the nonvolatile memory.
8. The search device of claim 1 , wherein the first comparison unit is provided in the nonvolatile memory.
9. The search device of claim 1 , wherein the search unit executes a key-value search.
10. The search device of claim 1 , wherein the nonvolatile memory is a NAND flash memory.
11. A search device comprising:
a determination unit which determines whether or not a difference between a received first key and a second key read from a nonvolatile memory is within a range of an error correction capability of an error correction process;
a correction unit which generates a third key by applying the error correction process to the second key if the determination unit determines that the difference is within the range; and
a search unit which reads data associated with the second key in the nonvolatile memory if the first key matches the third key.
12. A search method comprising:
generating a first comparison result by comparing a received first key with a second key read from a nonvolatile memory;
generating a determination result by determining, based on the first comparison result, whether or not a difference between the first key and the second key is within a range of an error correction capability of an error correction process;
generating a third key by applying the error correction process to the second key if the determination result indicates that the difference is within the range;
generating a second comparison result by comparing the first key with the third key; and
reading data associated with the second key in the nonvolatile memory if the second comparison result indicates a match.
13. The search method of claim 12 , further comprising:
generating a next first comparison result by comparing the first key with a next second key read from the nonvolatile memory if the determination result indicates that the difference is not within the range or if the second comparison result indicates a mismatch;
generating a next determination result by determining, based on the next first comparison result, whether or not a difference between the first key and the next second key is within the range;
generating a next third key by applying the error correction process to the next second key if the next determination result indicates that the difference between the first key and the next second key is within the range;
generating a next second comparison result by comparing the first key with the next third key; and
reading data associated with the next second key in the nonvolatile memory if the next second comparison result indicates a match.
14. The search method of claim 12 , wherein
the generating the first comparison result comprises calculating a Hamming distance based on the first key and the second key, and
the generating the determination result comprises determining whether the Hamming distance is within the range.
15. The search method of claim 12 , further comprising:
transmitting a signal indicating that data corresponding to the first key is not present in the nonvolatile memory to an information processing device, if all of candidate keys corresponding to the first key have been read from the nonvolatile memory and the data corresponding to the first key is not read.
16. The search method of claim 12 , further comprising:
correcting an error of the data read from the nonvolatile memory.
17. The search method of claim 12 , wherein the error correction process corrects the second key based on an error correcting code (ECC).
18. A search device comprising:
a first comparison unit which compares a received first key with a second key read from a nonvolatile memory;
a determination unit which determines, based on a first comparison result obtained by the first comparison unit, whether or not a difference between the first key and the second key is within a range of an error correction capability of an error correction process; and
a correction unit which generates a third key by applying the error correction process to the second key if the determination unit determines that the difference is within the range.