Kinetic data structure
ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಯು ನಿರಂತರವಾಗಿ ಚಲಿಸುತ್ತಿರುವ ಜ್ಯಾಮಿತೀಯ ವ್ಯವಸ್ಥೆಯ ಗುಣಲಕ್ಷಣವನ್ನು ಪತ್ತೆಹಚ್ಚಲು ಬಳಸುವ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಚಲನಶೀಲ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ದತ್ತಾಂಶ ರಚನೆಯು ಚಲಿಸುವ ಬಿಂದುಗಳ ಗುಂಪಿನ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಅನ್ನು ನಿರ್ವಹಿಸುತ್ತದೆ. ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಗಳ ಅಭಿವೃದ್ಧಿಯು ನಿರಂತರ ಚಲನೆಯಲ್ಲಿರುವ ಭೌತಿಕ ವಸ್ತುಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕಂಪ್ಯೂಟೇಶನಲ್ ಜ್ಯಾಮಿತಿ ಸಮಸ್ಯೆಗಳಿಂದ ಪ್ರೇರೇಪಿಸಲ್ಪಟ್ಟಿದೆ, ಉದಾಹರಣೆಗೆ ರೊಬೊಟಿಕ್ಸ್, ಅನಿಮೇಷನ್ ಅಥವಾ ಕಂಪ್ಯೂಟರ್ ಗ್ರಾಫಿಕ್ಸ್ನಲ್ಲಿ ಘರ್ಷಣೆ ಅಥವಾ ಗೋಚರತೆಯನ್ನು ಪತ್ತೆಹಚ್ಚುವುದು. ಒಂದು ಪರಿಚಿತ ಶೈಲಿಯಲ್ಲಿ, ಸಮಯದ ಕಾರ್ಯವಾಗಿ ಬದಲಾಗುತ್ತಿರುವ ಮೌಲ್ಯಗಳ ಗುಂಪನ್ನು ಹೊಂದಿರುವ ವ್ಯವಸ್ಥೆಗಳಲ್ಲಿ ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ ವ್ಯವಸ್ಥೆಯು ಕೆಲವು ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದೆ, ಮತ್ತು ಪ್ರತಿ ಮೌಲ್ಯಕ್ಕೂ, ಅದು ತಿಳಿದಿದೆ. ಕೈನೆಟಿಕ್ ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್ಗಳು ಪ್ರಸ್ತುತ ವರ್ಚುವಲ್ ಸಮಯದಲ್ಲಿ ಸಿಸ್ಟಮ್ನಲ್ಲಿ ಪ್ರಶ್ನೆಗಳನ್ನು ಮತ್ತು ಎರಡು ಹೆಚ್ಚುವರಿ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಅನುಮತಿಸುತ್ತವೆಃ : ಪ್ರಸ್ತುತ ಸಮಯಕ್ಕೆ ಮೌಲ್ಯದ ಪಥವನ್ನು ಬದಲಾಯಿಸುತ್ತದೆ. ಹೆಚ್ಚುವರಿ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸಬಹುದು. ಉದಾಹರಣೆಗೆ, ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಗಳನ್ನು ಹಲವುವೇಳೆ ಬಿಂದುಗಳ ಗುಂಪಿನೊಂದಿಗೆ ಬಳಸಲಾಗುತ್ತದೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ರಚನೆಯು ಸಾಮಾನ್ಯವಾಗಿ ಬಿಂದುಗಳನ್ನು ಸೇರಿಸಲು ಮತ್ತು ಅಳಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಸಾಂಪ್ರದಾಯಿಕ ದತ್ತಾಂಶ ರಚನೆಗಳೊಂದಿಗೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ ಚಲನಾತ್ಮಕ ದತ್ತಾಂಶ ರಚನೆಯು ಅದರಲ್ಲಿ ಸಂಗ್ರಹವಾಗಿರುವ ಮೌಲ್ಯಗಳನ್ನು ಸಮಯದೊಂದಿಗೆ ನಿರಂತರವಾಗಿ ಬದಲಾಯಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ತಾತ್ವಿಕವಾಗಿ, ನಿಗದಿತ ಸಮಯದ ಮಧ್ಯಂತರಗಳಲ್ಲಿ ಬಿಂದುಗಳ ಸ್ಥಾನವನ್ನು ಸ್ಯಾಂಪಲ್ ಮಾಡುವ ಮೂಲಕ ಮತ್ತು ಪ್ರತಿ ಬಿಂದುವನ್ನು "ಸ್ಥಿರ" (ಸಾಂಪ್ರದಾಯಿಕ) ದತ್ತಾಂಶ ರಚನೆಯಲ್ಲಿ ಅಳಿಸಿ ಮರು-ಸೇರಿಸುವ ಮೂಲಕ ಇದನ್ನು ಅಂದಾಜು ಮಾಡಬಹುದು. ಆದಾಗ್ಯೂ, ಅಂತಹ ವಿಧಾನವು ಯಾವ ಸಮಯದ ಮಧ್ಯಂತರವನ್ನು ಬಳಸಲಾಗುತ್ತದೆ ಎಂಬುದರ ಆಧಾರದ ಮೇಲೆ ಅತಿಯಾದ ಸ್ಯಾಂಪ್ಲಿಂಗ್ ಅಥವಾ ಅಂಡರ್ಸಾಂಪ್ಲಿಂಗ್ಗೆ ಗುರಿಯಾಗುತ್ತದೆ ಮತ್ತು ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಪನ್ಮೂಲಗಳನ್ನು ವ್ಯರ್ಥ ಮಾಡಬಹುದು. ಚಲನಾತ್ಮಕ ದತ್ತಾಂಶ ರಚನೆಗಳನ್ನು ನಿರ್ಮಿಸಲು ಈ ಕೆಳಗಿನ ಸಾಮಾನ್ಯ ವಿಧಾನವನ್ನು ಬಳಸಬಹುದುಃ ಪ್ರಸ್ತುತ ಸಮಯದಲ್ಲಿ ಸಿಸ್ಟಮ್ನಲ್ಲಿ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಸಂಗ್ರಹಿಸಿ. ಈ ದತ್ತಾಂಶ ರಚನೆಯು ಪ್ರಸ್ತುತ ವರ್ಚುವಲ್ ಸಮಯದಲ್ಲಿ ಸಿಸ್ಟಮ್ನಲ್ಲಿ ಪ್ರಶ್ನೆಗಳನ್ನು ಅನುಮತಿಸುತ್ತದೆ. ಪ್ರಮಾಣಪತ್ರಗಳೊಂದಿಗೆ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಹೆಚ್ಚಿಸಿ. ಪ್ರಮಾಣಪತ್ರಗಳು ದತ್ತಾಂಶ ರಚನೆಯು ನಿಖರವಾಗಿರುವ ಷರತ್ತುಗಳಾಗಿವೆ. ಪ್ರಮಾಣಪತ್ರಗಳೆಲ್ಲವೂ ಈಗ ನಿಜವಾಗಿವೆ, ಮತ್ತು ಒಂದು ಪ್ರಮಾಣಪತ್ರವು ಇನ್ನು ಮುಂದೆ ನಿಜವಾಗಿರದಿದ್ದಾಗ ಮಾತ್ರ ದತ್ತಾಂಶ ರಚನೆಯು ನಿಖರವಾಗಿರುವುದಿಲ್ಲ. ಪ್ರತಿ ಪ್ರಮಾಣಪತ್ರದ ವೈಫಲ್ಯದ ಸಮಯವನ್ನು ಲೆಕ್ಕ ಹಾಕಿ, ಅದು ನಿಜವಾಗದ ಸಮಯವನ್ನು ಲೆಕ್ಕ ಹಾಕಿ. ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಆದ್ಯತೆಯ ಸರತಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ, ಅವುಗಳ ವೈಫಲ್ಯದ ಸಮಯದ ಮೇಲೆ ಕೇಂದ್ರೀಕರಿಸಿ ಸಮಯಕ್ಕೆ ಮುನ್ನಡೆಯಲು, ಆದ್ಯತೆಯ ಸರತಿಯಲ್ಲಿನ ಅತ್ಯಂತ ಕಡಿಮೆ ವೈಫಲ್ಯದ ಸಮಯದೊಂದಿಗೆ ಪ್ರಮಾಣಪತ್ರವನ್ನು ನೋಡಿ. ಸಮಯಕ್ಕಿಂತ ಮೊದಲು ಪ್ರಮಾಣಪತ್ರವು ವಿಫಲವಾದರೆ, ಅದನ್ನು ಸರತಿಯಲ್ಲಿ ನಿಲ್ಲಿಸಿ ಮತ್ತು ವೈಫಲ್ಯದ ಸಮಯದಲ್ಲಿ ನಿಖರವಾಗಿರಲು ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಸರಿಪಡಿಸಿ ಮತ್ತು ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ನವೀಕರಿಸಿ. ಆದ್ಯತೆಯ ಸಾಲಿನಲ್ಲಿ ಕಡಿಮೆ ವೈಫಲ್ಯದ ಸಮಯವನ್ನು ಹೊಂದಿರುವ ಪ್ರಮಾಣಪತ್ರವು ಸಮಯದ ನಂತರ ವಿಫಲವಾಗುವವರೆಗೆ ಇದನ್ನು ಪುನರಾವರ್ತಿಸಿ. ಆದ್ಯತೆಯ ಸಾಲಿನಲ್ಲಿ ಕಡಿಮೆ ವೈಫಲ್ಯದ ಸಮಯವನ್ನು ಹೊಂದಿರುವ ಪ್ರಮಾಣಪತ್ರವು ಸಮಯದ ನಂತರ ವಿಫಲವಾದರೆ, ಎಲ್ಲಾ ಪ್ರಮಾಣಪತ್ರಗಳು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿದ್ದರೆ ದತ್ತಾಂಶ ರಚನೆಯು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಪ್ರಶ್ನೆಗಳಿಗೆ ಉತ್ತರಿಸಬಹುದು. ಘಟನೆಗಳ ಪ್ರಕಾರಗಳು ಪ್ರಮಾಣಪತ್ರ ವೈಫಲ್ಯಗಳನ್ನು "ಘಟನೆಗಳು" ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಕ್ರಿಯಾತ್ಮಕ ದತ್ತಾಂಶ ರಚನೆಯಿಂದ ನಿರ್ವಹಿಸಲ್ಪಡುವ ಗುಣಲಕ್ಷಣವು ಈವೆಂಟ್ ಸಂಭವಿಸಿದಾಗ ಬದಲಾಗದಿದ್ದರೆ ಈವೆಂಟ್ ಅನ್ನು ಆಂತರಿಕವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಈವೆಂಟ್ ಸಂಭವಿಸಿದಾಗ ಡೇಟಾ ರಚನೆಯಿಂದ ನಿರ್ವಹಿಸಲ್ಪಡುವ ಆಸ್ತಿಯು ಬದಲಾದರೆ ಈವೆಂಟ್ ಅನ್ನು ಬಾಹ್ಯವೆಂದು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆ. ಕಾರ್ಯಕ್ಷಮತೆ ಪ್ರಮಾಣಪತ್ರಗಳ ವಿಧಾನವನ್ನು ಬಳಸುವಾಗ, ಕಾರ್ಯಕ್ಷಮತೆಯ ನಾಲ್ಕು ಅಳತೆಗಳಿವೆ. ಒಂದು ಪ್ರಮಾಣವು ಪಾಲಿಲೋಗರಿಥಮಿಕ್ ಕಾರ್ಯವಾಗಿದ್ದರೆ, ಅಥವಾ ಅನಿಯಂತ್ರಿತವಾಗಿ ಚಿಕ್ಕದಾಗಿದ್ದರೆ, ವಸ್ತುಗಳ ಸಂಖ್ಯೆ ಎಲ್ಲಿದೆ ಎಂದು ನಾವು ಹೇಳುತ್ತೇವೆಃ ಪ್ರತಿಕ್ರಿಯಾತ್ಮಕ ಪ್ರತಿಕ್ರಿಯಾತ್ಮಕತೆಯು ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಸರಿಪಡಿಸಲು ಮತ್ತು ಪ್ರಮಾಣಪತ್ರವು ವಿಫಲವಾದಾಗ ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಹೆಚ್ಚಿಸಲು ಅಗತ್ಯವಿರುವ ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಮಯವಾಗಿದೆ. ನವೀಕರಣಕ್ಕೆ ಅಗತ್ಯವಿರುವ ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಮಯವು ಚಿಕ್ಕದಾಗಿದ್ದರೆ ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಯು ಸ್ಪಂದಿಸುತ್ತದೆ. ಸ್ಥಳೀಯತೆಯು ಯಾವುದೇ ಒಂದು ಮೌಲ್ಯವು ಒಳಗೊಂಡಿರುವ ಪ್ರಮಾಣಪತ್ರಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಚಲಿಸುವ ಬಿಂದುಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ರಚನೆಗಳಿಗೆ, ಯಾವುದೇ ಒಂದು ಬಿಂದುವು ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಪ್ರಮಾಣಪತ್ರಗಳನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಯಾವುದೇ ಒಂದು ಮೌಲ್ಯವು ಒಳಗೊಂಡಿರುವ ಪ್ರಮಾಣಪತ್ರಗಳ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯು ಚಿಕ್ಕದಾಗಿದ್ದರೆ ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಯು ಸ್ಥಳೀಯವಾಗಿರುತ್ತದೆ. ಸಾಂದ್ರತೆ ಎಂದರೆ ಯಾವುದೇ ಸಮಯದಲ್ಲಿ ದತ್ತಾಂಶ ರಚನೆಯನ್ನು ಹೆಚ್ಚಿಸಲು ಬಳಸುವ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಪ್ರಮಾಣಪತ್ರಗಳು. ಅದು ಬಳಸುವ ಪ್ರಮಾಣಪತ್ರಗಳ ಸಂಖ್ಯೆಯು ಸಾಂದ್ರವಾಗಿದ್ದರೆ ಅಥವಾ ಅನಿಯಂತ್ರಿತವಾಗಿ ಚಿಕ್ಕದಾಗಿದ್ದರೆ ಚಲನಶೀಲ ದತ್ತಾಂಶ ರಚನೆಯು ಸಾಂದ್ರವಾಗಿರುತ್ತದೆ. (ರೇಖೀಯ ಸ್ಥಳಕ್ಕಿಂತ ಒಂದು ಸಣ್ಣ ಅಂಶ) ದಕ್ಷತೆ ಎಂದರೆ ದತ್ತಾಂಶ ರಚನೆಯಲ್ಲಿನ "ಅಗತ್ಯ ಬದಲಾವಣೆಗಳ" ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಂಖ್ಯೆಗೆ ರಚನೆಯನ್ನು ಮುನ್ನಡೆಸಿದಾಗ ಸಂಭವಿಸಬಹುದಾದ ಅತ್ಯಂತ ಕೆಟ್ಟ ಘಟನೆಗಳ ಸಂಖ್ಯೆಯ ಅನುಪಾತ. "ಅಗತ್ಯ ಬದಲಾವಣೆಗಳ" ವ್ಯಾಖ್ಯಾನವು ಸಮಸ್ಯೆಯ ಮೇಲೆ ಅವಲಂಬಿತವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಚಲಿಸುವ ಬಿಂದುಗಳ ಗುಂಪಿನ ಚಲನೆಯ ಹೊದಿಕೆಯನ್ನು ನಿರ್ವಹಿಸುವ ಚಲನೆಯ ದತ್ತಾಂಶ ರಚನೆಯ ಸಂದರ್ಭದಲ್ಲಿ, ಸಮಯ ಮುಂದುವರೆದಂತೆ ಚಲನೆಯ ಹೊದಿಕೆಯು ಎಷ್ಟು ಬಾರಿ ಬದಲಾಗುತ್ತದೆ ಎಂಬುದು ಅಗತ್ಯ ಬದಲಾವಣೆಗಳ ಸಂಖ್ಯೆಯಾಗಿರುತ್ತದೆ. ಈ ಅನುಪಾತವು ಚಿಕ್ಕದಾಗಿದ್ದರೆ ಚಲನೆಯ ದತ್ತಾಂಶ ರಚನೆಯು ಪರಿಣಾಮಕಾರಿಯಾಗಿದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಪಥಗಳ ವಿಧಗಳು ನಿರ್ದಿಷ್ಟ ಚಲನೆಯ ದತ್ತಾಂಶ ರಚನೆಯ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಕೆಲವು ರೀತಿಯ ಪಥಗಳಿಗೆ ವಿಶ್ಲೇಷಿಸಬಹುದು. ವಿಶಿಷ್ಟವಾಗಿ, ಈ ಕೆಳಗಿನ ವಿಧದ ಪಥಗಳನ್ನು ಪರಿಗಣಿಸಲಾಗುತ್ತದೆಃ ಅಫೈನ್ಃ (ರೇಖೀಯ ಕಾರ್ಯಗಳು) ಬೌಂಡೆಡ್-ಡಿಗ್ರಿ ಬೀಜಗಣಿತಃ (ಬೌಂಡೆಡ್ ಡಿಗ್ರಿಯ ಬಹುಪದೀಯ ಕಾರ್ಯಗಳು) ಕೆಲವು ಸ್ಥಿರವಾದವುಗಳಿಗೆ. ಸೂಡೋ-ಆಲ್ಜಿಬ್ರಾಯಿಕ್ಃ ಯಾವುದೇ ಬಡ್ಡಿ ಪ್ರಮಾಣಪತ್ರವು ನಿಜ ಮತ್ತು ಸುಳ್ಳು ಸಮಯಗಳ ನಡುವೆ ತಿರುಗುವಂತಹ ಪಥಗಳು. ಉದಾಹರಣೆಗಳು ಕೈನೆಟಿಕ್ ಪಂದ್ಯಾವಳಿ ಕೈನೆಟಿಕ್ ವಿಂಗಡಿಸಲಾದ ಪಟ್ಟಿ ಕೈನೆಟಿಕ್ ಹೀಪ್ ಕೈನೆಟಿಕ್ ಕನ್ವೆಕ್ಸ್ ಹಲ್ ಕೈನೆಟಿಕ್ ಹತ್ತಿರದ ಜೋಡಿ ಕೈನೆಟಿಕ್ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಕೈನೆಟಿಕ್ ಯೂಕ್ಲಿಡಿಯನ್ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಉಲ್ಲೇಖಗಳು ಕೈನೆಟಿಕ್ ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್ಗಳು